[Coding028] Sort - 基数排序

Radix-sort

More coding records

Get the knowledge flowing and circulating! :)

目录

标题：基数排序

Words & phrases

radix 美/ ˈreɪdɪks /

• n.根；[数]基数

Radix sorting is widely used for its high efficiency.

基数排序由于其效率高而被广泛应用。

概念

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

• 由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

实现方法

1. 将所有待比较数值（正整数）统一为同样的数位长度（数位较短的数前面补零）。

2. 然后，从最低位开始，依次进行一次排序。

这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

---

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital）：

• LSD：LSD的排序方式由键值的最右边开始；

• MSD：与LSD相反，由键值的最左边开始。

——维基百科

Radix-Sort Variation 1

variation 美/ ˌveriˈeɪʃ(ə)n /

• n.变化，变动；变奏曲；变化，变异；（天文）二均差；（数）变分，变差；磁偏角；（芭蕾）单人舞

Variation among humans is limited to the possible permutations of our genes.

人类的变化形式受限于我们基因可能的那些排列。

• Uses bucket-sort as the stable sorting algorithm.

  使用桶排序作为稳定排序算法。

• Applicable to tuples where the keys in each dimension $i$$i$ are integers in the range $[0,N-1]$$[0, N − 1]$

  适用于这样的元组，元组的键在每个维度上都是$[0,N-1]$$[0, N − 1]$中的整数。

• runs in $O(d(n+N))$$O(d( n + N))$

  运行时间复杂度为$O(d(n+N))$$O(d( n + N))$。

Radix-Sort Variation 2

• Consider a sequence of $n$$n$ $b$$b$-bit integers $x=x_{b-1}\dots x_1{x}_0$$x = x_{b − 1} … x_1x_0$

  考虑一个有 $n$$n$ 个整数的序列，这个序列里的每个整数都有 $b$$b$ 位：123，345，888，...。

• We represent each element as a $b$$b$-tuple of integers in the range $[0,1]$$[0, 1]$ and apply radix-sort with $N=2$$N = 2$

  把每个元素表示为一个 $b$$b$ 元组，元组中的每个整数值取值为 $[0,1]$$[0, 1]$。

• runs in $O(bn)$$O(bn)$ time

  时间复杂度为 $O(bn)$$O(bn)$ 。

• sorts Java ints (32-bits) in linear time

实例

Sorting a sequence of 4-bit integers

Radix-Sort Variation 3

The keys are integers in the range $[0,N^2-1]$$[0, N^2 − 1]$

We represent a key as a 2-tuple of digits in the range [0, N − 1] and apply radish-sort i.e. we write it in base $N$$N$ notation:

现在考虑一下泛化情况（即，以N为基的radish-sort），十进制的整数就拆成多个十进制的单个数，例如75 →（7, 5）。

• Example (N = 10):

  • 75 → (7, 5)

    十进制的数：$75=7\ast {10}^1+5\ast {10}^0$$75=7*10^1+5*10^0$

• Example (N = 8):

  • 35 → (4, 3)

    八进制的数：$35=4\ast 8^1+3\ast 8^0$$35=4*8^1+3*8^0$

• The running time is $O(n+N)$$O( n + N)$

  运行时间复杂度为$O(n+N)$$O( n + N)$

• Can be extended to integer keys in the range $[0,N^d-1]$$[0, N^d − 1]$

  $d$$d$ 代表位数，$N$$N$ 代表基数。例如，$d=2$$d=2$，$N=10$$N=10$时，表示2位的十进制数0~99。

  $[0,N^d-1]⟺[0,{10}^2-1]⟺[0,99]$$[0, N^d − 1] \iff [0, 10^2 − 1] \iff [0, 99]$

实例 (N = 10)

keys are integers in the range [0, 99]

拓展(Extensions)

Radix-sort string variation（适用于字符串的基数排序的变形）

• The keys are strings of $d$$d$ characters each

  每个键是包含 $d$$d$ 个字符的字符串。

• We represent each key by a $d$$d$-tuple of integers, where is the ASCII (8-bit integer) or Unicode (16-bit integer) representation of the $i$$i$-th character and apply radix-sort variation 1.

  把每个字符串表示为一个 $d$$d$ 维元组，元组中的每个数表示对应的字符的ASCII码或者Unicode码。
  例如，字符串 “abc” 表示为 (1,2,3)，因为a是第一个，b是第二个...

实例(Example)

Use the last variation to sort the following strings: